package code;

import java.util.Arrays;

public class Code11 {

	/*
	 * 对于这种类型的题目，所求解是ans=x&y同时决定，可以归纳为二元约束问题。
	 * 一般的解法，很明显是，先分解掉一个x约束，再由剩下的变量y，来找最优的解。
	 * 此题目意思是：在一个水平面上，有n根平行与y轴的线段，起点是[i,0]，终点是[0,height[i]],
	 * 取其中的两条线段，能够容纳最多的水.
	 * 简化为 ans=max{(j-i)*min(height[i],height[j])}，其中0=<i,j<n
	 * 
	 * 暴力解法枚举所有的(i,j)组合，标准的时间复杂度O(n*n),TLE
	 * 最关键的问题，我们不知道height[j]是否大于height[i],所以我们也没法选取j-i的最大值，来
	 * 得到最终ans的最大值
	 * 那么我们可以保留每个（height[i],i），根据height排序
	 * 选取height[j]>=height[i], 再选取Min[index[i+1,n]],或Max[index[i+1,n]]，
	 * 最后可以推导出最优的解。
	 * 具体细节，还需要自己想清楚
	 */
	class dual implements Comparable<dual>{
		int val;
		int idx;
		
		public dual(int a,int b){
			val=a;
			idx=b;
		}
		@Override
		public int compareTo(dual o) {
			// TODO Auto-generated method stub
			return val-o.val;
		}
	}
    public int maxAreaII(int[] height) {
    	int ans=0;
    	int n=height.length;
    	dual[] list=new dual[n];
    	int i,j;
    	for(i=0;i<n;i++)
    		list[i]=new dual(height[i],i);
    	
    	Arrays.sort(list);
    	int[] maxIdx=new int[n];
    	int[] minIdx=new int[n];
    	for(i=n-1;i>=0;i--){
    		if(i==n-1){
    			maxIdx[i]=list[i].idx;
    			minIdx[i]=list[i].idx;
    		}
    		else{
    			maxIdx[i]=maxIdx[i+1]>list[i].idx?maxIdx[i+1]:list[i].idx;
    			minIdx[i]=minIdx[i+1]<list[i].idx?minIdx[i+1]:list[i].idx;
    		}
    	}
    	for(i=0;i<n-1;i++){
    		int a=Math.abs(list[i].idx-maxIdx[i+1]);
    		int b=Math.abs(list[i].idx-minIdx[i+1]);
    		a=a>b?a:b;
    		a*=list[i].val;
    		if(ans<a)
    			ans=a;
    	}
    	return ans;
    }
    /*
     * 其实官方版的，效率更高O(n)
     * 贪心
     * 先想象一下，什么时候，最有可能出现最优解，就是我先选0与n-1的两个元素
     * 然后，将两块隔板往内部移动，短的板子被往里移动，最后所得到的解为最优解
     */
    public int maxArea(int[] height) {
    	int ans=0;
    	int n=height.length;
    	int left=0,right=n-1;
    	while(left<right){
    		int temp=height[left]<height[right]?height[left]:height[right];
    		temp*=(right-left);
    		if(ans<temp)
    			ans=temp;
    		if(height[left]<height[right]){
    			left++;
    		}
    		else
    			right--;
    	}
    	return ans;
    }
    public static void main(String[] args){
    	int[] height={5,4,3,7,6};
    	new Code11().maxArea(height);
    }
	
}
